//https://leetcode.cn/problems/copy-list-with-random-pointer/

struct Node* copyRandomList(struct Node* head) {

    //在原节点后面拷贝一个原节点
    struct Node* cur = head;
    while (cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        if (copy == NULL)
        {
            perror("malloc fail\n");
        }
        struct Node* next = cur->next;
        copy->val = cur->val;

        cur->next = copy;
        copy->next = next;

        cur = next;
    }

    //寻找拷贝节点的random
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }

        else
        {
            copy->random = cur->random->next;
        }

        cur = copy->next;
    }

    //取下拷贝节点依次尾插成新链表，恢复原链表
    cur = head;
    struct Node* copyhead, * copytail;
    copyhead = NULL;
    copytail = NULL;

    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

        if (copyhead == NULL)
        {
            copyhead = copytail = copy;
        }

        else
        {
            copytail->next = copy;
            copytail = copy;
        }

        //恢复原链表
        cur->next = next;
        cur = next;


    }

    return copyhead;

}